package com.example.interview.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定单向链表的头指针和一个结点指针，定义一个函数在0(1)时间删除该结点,
 * 
 * @Description: TODO
 * @author gaobing
 * @date 2018年10月9日 下午3:23:43
 * 
 */
public class Test13DeleteListNode {

	/**
	 * 链表
	 * 
	 * @Description: TODO
	 * @author gaobing
	 * @date 2018年10月9日 下午3:24:33
	 *
	 */
	public static class ListNode {
		int value; // 保存链表的值
		ListNode next;// 下一个节点
	}

	/**
	 * * 给定单向链表的头指针和一个结点指针，定义一个函数在0(1)时间删除该结点, *
	 * 【注意1：这个方法和文本上的不一样，书上的没有返回值，这个因为JAVA引用传递的原因， *
	 * 如果删除的结点是头结点，如果不采用返回值的方式，那么头结点永远删除不了】 *
	 * 【注意2：输入的待删除结点必须是待链表中的结点，否则会引起错误，这个条件由用户进行保证】
	 * 
	 * @param head
	 * @param toBeDeleted
	 * @return
	 */
	public static ListNode deleteNode(ListNode head, ListNode toBeDeleted) {
		// 如果输入参数有空值就返回表头节点
		if (head == null || toBeDeleted == null) {
			return head;
		}
		// 如果删除的是头节点，直接返回头节点的下一个节点
		if (head == toBeDeleted) {
			return head.next;
		}
		// 下面的情况链表至少有2个节点
		// 在多个节点的情况下，如果删除的是最后一个元素
		if (toBeDeleted.next == null) {
			// 从头开始遍历，找待删除元素的前置节点
			ListNode temp = head;
			while (temp.next != toBeDeleted) {
				temp = temp.next;
			}
			// 删除待节点
			temp.next = null;
		} else {
			// 在多个节点的情况下，如果删除的是某个中间节点
			// 将下一个节点的值输入到当前待删除节点
			toBeDeleted.value = toBeDeleted.next.value;
			// 修改指引
			toBeDeleted.next = toBeDeleted.next.next;
		}

		// 返回删除后的链表头节点
		return head;
	}

	/**
	 * 输出链表元素值
	 * 
	 * @param head
	 */
	public static void printList(ListNode head) {
		while (head != null) {
			System.out.print(head.value + "->");
			head = head.next;
		}
		System.out.println("null");
	}

	public static void main(String[] args) {
		ListNode head = new ListNode();
		head.value = 1;
		head.next = new ListNode();
		head.next.value = 2;
		head.next.next = new ListNode();
		head.next.next.value = 3;
		head.next.next.next = new ListNode();
		head.next.next.next.value = 4;
		ListNode middle = head.next.next.next.next = new ListNode();
		head.next.next.next.next.value = 5;
		head.next.next.next.next.next = new ListNode();
		head.next.next.next.next.next.value = 6;
		head.next.next.next.next.next.next = new ListNode();
		head.next.next.next.next.next.next.value = 7;
		head.next.next.next.next.next.next.next = new ListNode();
		head.next.next.next.next.next.next.next.value = 8;
		ListNode last = head.next.next.next.next.next.next.next.next = new ListNode();
		head.next.next.next.next.next.next.next.next.value = 9;

		head = deleteNode(head, null); // 删除的结点为空
		printList(head); 
		head = deleteNode(head, head); // 删除头结点
		printList(head);
		head = deleteNode(head, last); // 删除尾结点
		printList(head);
		head = deleteNode(head, middle); // 删除中间结点
		printList(head);
		ListNode node = new ListNode();
		node.value = 12;
		head = deleteNode(head, node); // 删除的结点不在链表中
		printList(head);
		
		Map<String, String> map=new HashMap<>();

	}
}
